Elliptic curves over finite fields GF(2^n) play a prominent role in moderncryptography. Published quantum algorithms dealing with such curves build on ashort Weierstrass form in combination with affine or projective coordinates. Inthis paper we show that changing the curve representation allows a substantialreduction in the number of T-gates needed to implement the curve arithmetic. Asa tool, we present a quantum circuit for computing multiplicative inverses inGF(2^n) in depth O(n log n) using a polynomial basis representation, which maybe of independent interest.
展开▼
